package features.advance.leetcode.dynamicProgramming;

import features.advance.leetcode.util.StringUtil;
import lombok.Getter;
import lombok.Setter;

import java.util.Arrays;

/**
 * 53. 最大子序和
 * 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
 * 输出：6
 * 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
 * 示例 2：
 *
 * 输入：nums = [1]
 * 输出：1
 * 示例 3：
 *
 * 输入：nums = [0]
 * 输出：0
 * 示例 4：
 *
 * 输入：nums = [-1]
 * 输出：-1
 * 示例 5：
 *
 * 输入：nums = [-100000]
 * 输出：-100000
 *
 *
 * 提示：
 *
 * 1 <= nums.length <= 3 * 104
 * -105 <= nums[i] <= 105
 *
 *
 * 进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。
 * @author LIN
 * @date 2021/04/02
 */
public abstract class Solution53 {

    public abstract SubArray maxSubArray(int[] nums, boolean dummy);

    public int maxSubArray(int[] nums) {
        int pre = 0;
        if (nums == null) return 0;
        int maxNum = nums[0];
        for(int i=0; i<nums.length;i++){
            int x = nums[i];
            pre = Math.max(pre + x,x);
            maxNum = Math.max(pre,maxNum);
        }

        return maxNum;
    }
    class SubArray{
        @Getter@Setter
        private int startIndex = 0;
        @Getter@Setter
        private int endIndex = -1;

        @Getter@Setter
        private int[] array;

        public int[] get(){
            if(array == null || array.length == 0){
                return array;
            }
            if(endIndex > startIndex){
                return Arrays.copyOfRange(array,startIndex,endIndex + 1);
            }else {
                return null;
            }
        }

        public Integer getSum(){
            int[] ints = get();
            int sum = 0;
            if(ints != null){
                for (int i = 0; i < ints.length; i++) {
                    sum+=ints[i];
                }
                return sum;
            }else{
                return null;
            }
        }
    }

    public static void main(String[] args) {
        String str = "[5, 1, -12, 7, 9, 6, 16, 22, 21, 29, -14, 10, 12]";
        int[] arr = StringUtil.parseStrToArr(str);
        System.out.println(Arrays.toString(arr));
        Solution53 solution53 = new Solution53() {

            @Override
            public SubArray maxSubArray(int[] nums, boolean dummy) {
                /**
                 * 获取最大子序列的索引区间lindex,rindex
                 *
                 *
                 */
                SubArray subArray = new SubArray();
                subArray.setArray(nums);
                int pre = nums[0];
                int max = pre;
                int lindex = 0,ltemp = lindex;
                int rindex = 0;
                for (int i = 0; i < nums.length; i++) {
                    int x = nums[i];
                    if(pre+x >= x){
                        pre = pre+x;
                    }else{
                        pre = x;
                        ltemp = i;
                    }
                    if(max <= pre){
                        max = pre;
                        lindex = ltemp;
                        rindex = i;
                    }
                }
                subArray.setStartIndex(lindex);
                subArray.setEndIndex(rindex);

                return subArray;
            }
        };
        SubArray maxSubArray = solution53.maxSubArray(arr,true);
        int i = solution53.maxSubArray(arr);
        System.out.println(i+":"+(i == maxSubArray.getSum()));
        System.out.println(Arrays.toString(maxSubArray.get()));
    }
}
